package javatest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import util.PrintArray;

public class AlgorithmTest {
    public static void main(String[] args) {
        AlgorithmTest object = new AlgorithmTest();
//        System.out.println(object.printAllStep2(11, 1, 2));
//        object.printAllStep3(11, 1, 2);

//        String s = "ab  zxc ds   aa  ";
//        object.moveSpace(s.toCharArray());

//        int[] array = {1, 3, 4, 5, 6, 7, 9, 10};
//        System.out.println(object.getMinimumLength(array));

        int[] array = {17,13,11,2,3,5,7};
        object.deckRevealedIncreasing(array);
    }

    //
//    n阶台阶，可以走a步，也可以走b步，打印所有可能的走法。
//    n=11,a=3,b=5 输出 335 353 533（没有搞出来），
//    然后说搞不出来 那就打印一下一共有多少种走法也可以（也没搞出来 😣）
    // 先写一共有多少种走法，递归方式
    public int printAllStep(int n, int a, int b) {
        if (n == a || n == b) {
            return 1;
        } else if (n < Math.max(a, b)) {
            return 0;
        }
        return printAllStep(n - a, a, b) +  printAllStep(n - b, a, b);
    }

    // 循环方式
    public int printAllStep2(int n, int a, int b) {
        if (n <= 0) {
            return 0;
        }
        int max = Math.max(a, b);
        int min = Math.min(a, b);
        int[] step = new int[n + 1];
        step[0] = 1;
        for (int i = min; i <= max; i++) {
            int aStep = 0;
            if (i >= a) {
                aStep = step[i - a];
            }
            int bStep = 0;
            if (i >= b) {
                bStep = step[i - b];
            }
            step[i] = aStep + bStep;
        }
        for (int i = max + 1; i <= n; i++) {
            step[i] = step[i - a] + step[i - b];
        }
        PrintArray.printArray(step);
        return step[n];
    }

    // 打印所有可能的路径
    public void printAllStep3(int n, int a, int b) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> curStep = new ArrayList<>();
        list.add(a);
        list.add(b);
        printAllStepImpl(n, list, curStep);
        System.out.println("real Count: " + count);
    }

    int count = 0;

    public void printAllStepImpl(int n, List<Integer> steps, List<Integer> curStep) {
        if (n < 0) {
            return;
        }
        if (n == 0) {
            System.out.println(Arrays.toString(curStep.toArray()));
            count++;
            return;
        }
        for (int i = 0; i < steps.size(); i++) {
            curStep.add(steps.get(i));
            printAllStepImpl(n - steps.get(i), steps, curStep);
            curStep.remove(curStep.size() - 1);
        }
    }


//    算法：给一个字符数组，有两个连续空格的话，需要去空格，将空格放到数组最后，不允许用额外空间；
    // 这道题由于是网上看的，有些条件不知道怎么处理：连续三个空格，是咋处理
    // 这里处理成大于两个的都后移
    public void moveSpace(char[] chars) {
        int start = 0;
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == ' ' && chars[i + 1] == ' ') {
                while (i < chars.length && chars[i] == ' ') {
                    i++;
                }
            }
            if (i < chars.length) {
                chars[start++] = chars[i];
            }
        }
        for (int i = start; i < chars.length; i++) {
            chars[i] = ' ';
        }
        for (int i = 0; i < chars.length; i++) {
            System.out.print(chars[i]);
        }
        System.out.println();
    }

    /**
     * 获取最小需要排序的子数组的长度
     */
    public int getMinimumLength(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        // 找到某个数，这个数和它右边的数比左边的都大
        int rightIndex = -1;
        int curMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= curMax) {
                curMax = nums[i];
            } else {
                rightIndex = i;
            }
        }
        int leftIndex = -1;
        int curMin = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] <= curMin) {
                curMin = nums[i];
            } else {
                leftIndex = i;
            }
        }
        System.out.println("rightIndex: " + rightIndex + " leftIndex: " + leftIndex);
        // 如果为-1，说明是严格递增的，return 0
        if (rightIndex == -1) {
            return 0;
        }
        return rightIndex - leftIndex + 1;
    }

    public int[] deckRevealedIncreasing(int[] deck) {
        if (deck == null) {
            return null;
        }
        LinkedList<Integer> deque = new LinkedList<>();
        Arrays.sort(deck);
        for (int i = 0; i < deck.length; i++) {
            deque.addLast(i);
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (!deque.isEmpty()) {
            list.add(deque.removeFirst());
            if (!deque.isEmpty()) {
                deque.addLast(deque.removeFirst());
            }
        }
        int[] res = new int[deck.length];
        for (int i = 0; i < list.size(); i++) {
            res[list.get(i)] = deck[i];
        }
        System.out.println(Arrays.toString(list.toArray()));
        PrintArray.printArray(res);
        PrintArray.printArray(deck);
        return res;
    }
}
